#include<stdio.h>
int main() {
	int i, j, k, m, n, s;
	scanf("%d", &s);
	while (s--) {
		scanf("%d%d", &n, &m);
		for (i = m, j = 0; i <= n; i++)
			for (k = i; !(k % m); j++)
				k = k / m;
		printf("%d\n", j);
	}
	return 0;
}
